|
|
1.
用最小回路求两个简单多边形的交、并、差集
赵军 刘荣珍
计算机应用
2012, 32 (11):
3164-3167.
DOI: 10.3724/SP.J.1087.2012.03164
针对求两个简单多边形交、并、差集问题，提出一种基于最小回路的新算法。首先，将初始多边形P和Q初始化为逆时针方向，并将两个多边形交点处的关联边排序。然后，从各个交点出发利用最小转角法搜索最小回路，并根据这些最小回路中包含P和Q边的方向性对它们进行分类。最终，不同类别的最小回路将对应P和Q的交、并、差集。算法的时间复杂度为O((n+m+k)logd)，其中n、m 分别是P和Q的顶点数，k是两多边形的交点数，d为将多边形分割的单调链数。算法几何意义明显，对于多边形布尔运算中的重合顶点、重合边等奇异情形，具有较好的适应性。
参考文献 |
相关文章 |
多维度评价
|
|
